package com.kznnc.data_structure.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU算法  LRU缓存队列
 * 参考链接：https://baijiahao.baidu.com/s?id=1633118537743651176&wfr=spider&for=pc
 */
public class LRUAlgorithm {


    Node head;
    Node tail;
    int limit;
    Map<String, Node> hashMap;


    public LRUAlgorithm(int limit) {
        this.limit = limit;
        this.hashMap = new HashMap<>(limit);
    }


    public void addNode(String value) {

        if (head == null) {
            Node node = new Node(value);
            head = node;
            tail = node;
            hashMap.put(value, node);
        } else {
            if (hashMap.containsKey(value)) {
                // 节点存在相当于 删除已存在的 加入到链表tail
                refreshNode(value);
            } else {
                Node node = new Node(value);
                node.pre = tail;
                tail.next = node;
                tail = node;
                hashMap.put(node.pre.value, node.pre);
                hashMap.put(node.value, node);
            }
        }

    }


    private void refreshNode(String value) {
        deleteNode(value);
        addNode(value);
    }

    public void deleteNode(String value) {
        if (!hashMap.containsKey(value)) {
            return;
        }
        Node node = hashMap.get(value);
        Node pre = node.pre;
        Node next = node.next;
        if (pre == null){
            head = next;
        }else {
            pre.next = next;
        }
        if (next == null){
            tail = pre;
        }else {
            next.pre = pre;
        }
        node.pre = null;
        node.next = null;
        hashMap.remove(value);
    }

    public String getLastNode() {
        if (tail == null) {
            return null;
        }
        return tail.value;
    }

    public void accessNode(String value) {
        if (!hashMap.containsKey(value)) {
            return;
        }
        refreshNode(value);
    }


    public void printData() {
        StringBuilder stringBuilder = new StringBuilder();
        Node node = head;
        while (node != null) {
            stringBuilder.append(node.value).append(",");
            node = node.next;
        }
        System.out.println(stringBuilder.toString());
    }

    static class Node {

        public Node pre;
        public Node next;
        public String value;
        public Node(String value) {
            this.value = value;
        }
    }

}
